package 力扣面试经典150;

/**
 * Created with IntelliJ IEDA.
 * Description:
 * User:86186
 * Date:2024-03-21
 * Time:16:37
 */

/**
 * 力扣面试经典150:82. 删除排序链表中的重复元素 II
 * 中等
 * 相关标签
 * 相关企业
 * 给定一个已排序的链表的头 head ， 删除原始链表中所有重复数字的节点，只留下不同的数字 。返回 已排序的链表 。
 * 示例 1：
 * 输入：head = [1,2,3,3,4,4,5]
 * 输出：[1,2,5]
 */
public class deleteDuplicates {
    public static void main(String[] args) {
        int[] nodes = {1, 2, 3, 3, 4, 4, 5};
        ListNode head = createLinkedList(nodes);
        deleteDuplicates(head);
    }
    public static ListNode createLinkedList(int[] nodes) {
        ListNode dummy = new ListNode(0);
        ListNode current = dummy;
        for (int node : nodes) {
            current.next = new ListNode(node);
            current = current.next;
        }
        return dummy.next;
    }
    public static ListNode deleteDuplicates(ListNode head) {
        /*超出时间限制
        if(head == null)return head;
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode pre = dummy;
        ListNode cur = head;

        while(cur.next != null){
            ListNode tmp = cur.next;
            if(cur.val == tmp.val){
                while(cur.val == tmp.val && tmp.next != null) tmp = tmp.next;
                if(cur.next == tmp){
                    pre.next = cur;
                    pre = pre.next;
                }else{
                    pre.next = tmp;
                }
            }else{
                pre = cur;
                cur = cur.next;
            }
        }
        return dummy.next ;*/
        if (head == null) return head;
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode pre = dummy;
        ListNode cur = head;
        ListNode tmp = null;
        while (cur != null) {
            tmp = cur.next;
            while (tmp != null && cur.val == tmp.val) {
                tmp = tmp.next;
            }
            if (cur.next == tmp) {
                pre.next = cur;
                pre = pre.next;
            } else {
                pre.next = tmp;
            }
            cur = pre.next;
        }
        return dummy.next;
    }
}
